package com.LeetCode.why530;

import com.LeetCode.why98.TreeNode;

import java.util.LinkedList;

public class MInDIffInBST {
    public int getMinimumDifference(TreeNode root) {
        //计算最小差值的思路：找出当前节点大于它的最小值和小于它的最大值。然后遍历一次就行了！
        int result = Integer.MAX_VALUE;
        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        while (queue.size() > 0 && result > 1) {
            TreeNode node = queue.remove();
            if (node.left != null && node.right != null) {
                int tmp = min(minRight(node.right) - node.val, node.val - maxLeft(node.left));
                result = min(result, tmp);
                queue.add(node.left);
                queue.add(node.right);
            } else if (node.left != null) {
                result = min(result, node.val - maxLeft(node.left));
                queue.add(node.left);
            } else if (node.right != null) {
                result = min(result, minRight(node.right) - node.val);
                queue.add(node.right);
            }

        }
        return result;
    }

    public int minRight(TreeNode node) {
        while (node.left != null) {
            node = node.left;
        }
        return node.val;
    }

    public int maxLeft(TreeNode node) {
        while (node.right != null) {
            node = node.right;
        }
        return node.val;
    }

    public int min(int a, int b) {
        return a > b ? b : a;
    }


    public static void main(String[] arg) {

    }

}
